// 笔试强训2025/3/14
// 腐烂的苹果

class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param grid int整型vector<vector<>> 
         * @return int整型
         */
        void dediate(vector<vector<int>>& grid, vector<vector<int>>& time, int i, int j, int last)
        {
            time[i][j] = min(time[i][j], last);
            if(i > 0 && grid[i - 1][j] == 1)
            {
                grid[i - 1][j] = 2;
                dediate(grid, time, i - 1, j, time[i][j] + 1);
                grid[i - 1][j] = 1;
            }
            if(i < grid.size() - 1 && grid[i + 1][j] == 1)
            {
                grid[i + 1][j] = 2;
                dediate(grid, time, i + 1, j, time[i][j] + 1);
                grid[i + 1][j] = 1;
            }
            if(j > 0 && grid[i][j - 1] == 1)
            {
                grid[i][j - 1] = 2;
                dediate(grid, time, i, j - 1, time[i][j] + 1);
                grid[i][j - 1] = 1;
            }
            if(j < grid[i].size() - 1 && grid[i][j + 1] == 1)
            {
                grid[i][j + 1] = 2;
                dediate(grid, time, i, j + 1, time[i][j] + 1);
                grid[i][j + 1] = 1;
            }
        }
        
        int rotApple(vector<vector<int> >& grid) {
            // write code here
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> time(m, vector<int>(n, 2001));
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(grid[i][j] == 2)
                        dediate(grid, time, i, j, 0);
                }
            }
            int ans = 0;
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(grid[i][j] == 1)
                    {
                        if(time[i][j] == 2001)
                            return -1;
                        ans = max(ans, time[i][j]);
                    }
                }
            }
            return ans;
        }
    };